package io.tec.cloud.algorithm.c01_v20220601;

import io.tec.cloud.algorithm.AlgorithmUtil;

/**
 * 定义何为局部最小值：
 * arr[0] < arr[1]，0位置是局部最小；
 * arr[N-1] < arr[N-2]，N-1位置是局部最小；
 * arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
 * 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回
 */
public class T7_BSAwesome {

    /**
     * 递归：算法错误
     * @param arr
     * @return
     */
    public static int getLessIndex1(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        // TODO 不要用递归，arr[0], arr[length -1已经判断过了，后续递归中，只要在1~arr.length-2找即可。
        return bs(arr, 1, arr.length - 2);

    }

    /**
     * 从 l、r范围上，找局部最小值
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int bs(int[] arr, int l, int r) {
        // base case
        if (l >= r) {
            return l;
        }
        int mid = l + ((r - l) >> 1);
        if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
            return mid;
        } else if (arr[mid] > arr[mid - 1]) {
            return bs(arr, l, mid - 1);
        } else if (arr[mid] > arr[mid + 1]) {
            return bs(arr, mid + 1, r);
        }
        return -1;
    }

    public static int getLessIndex2(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        int n = arr.length;
        if (arr[n - 1] < arr[n - 2]) {
            return n - 1;
        }

        int l = 1;
        int r = n - 1;
        // TODO 边界条件
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] > arr[mid - 1]) {
                r = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        // TODO 边界条件
        return l;
    }

    public static int getLessIndex3(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        int n = arr.length;
        if (arr[n - 1] < arr[n - 2]) {
            return n - 1;
        }

        int l = 1;
        int r = n - 1;
        // TODO 边界条件
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] > arr[mid - 1]) {
                r = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        // TODO 边界条件
        return -1;
    }


    public static void main(String[] args) {
        int testTimes = 5000000;
        int maxValue = 500;
        int maxLength = 50;
        for (int i = 0; i < testTimes; i++) {
//            int[] original = {};
            int[] original =  generatorArray(maxValue, maxLength);
//            int[] original = {0, -317, -300};
//            int[] original = {2,1,2,3,4,5,6,7,8,9,10};
//            int[] original = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2};
            try {
                final int globalMinIndex1 = getLessIndex1(original);
                final int globalMinIndex2 = getLessIndex2(original);
                final int globalMinIndex3 = getLessIndex3(original);
                final int globalMinIndex4 = getLessIndex4(original);
//            final int globalMinIndex = getGlobalMinIndex(original);
//            SortTestUtil.p(original);
//            System.out.println(globalMinIndex);
                if (!test(original, globalMinIndex1)
                        || !test(original, globalMinIndex2)
                        || !test(original, globalMinIndex3)
                        || !test(original, globalMinIndex4)) {
                    System.out.println("error");
                    return;
                }
            } catch (Exception e) {
                AlgorithmUtil.printArray(original);
                break;
            }
        }

        System.out.println("finish");
    }

    public static boolean test(int[] arr, int minIndex) {
        if (arr == null || arr.length == 0) {
            return true;
        }

        if (minIndex < 0) {
            return false;
        }

        if (arr.length == 1) {
            return true;
        }

        if (minIndex == 0) {
            return arr[0] < arr[1];
        }

        if (minIndex == arr.length - 1) {
            return arr[arr.length - 1] < arr[arr.length - 2];
        }
        return arr[minIndex] < arr[minIndex - 1] && arr[minIndex] < arr[minIndex + 1];
    }

    private static int[] generatorArray(int maxValue, int maxLength) {

        int[] arr = new int[(int) (Math.random() * maxLength + 1)];
        arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    /**
     * 知乎上的暴力
     *
     * @param arr
     * @return
     */
    public static int getLessIndex4(int[] arr) {
        if (arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        if (arr.length > 1 && arr[0] < arr[1]) {
            return 0;
        }
        if (arr.length > 1 && arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                return i;
            }
        }

        return -1;
    }

}
